package org.usmile.algorithms.leetcode.middle;

/**
 * 670. 最大交换
 *
 * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
 *
 * 示例 1 :
 * 输入: 2736
 * 输出: 7236
 * 解释: 交换数字2和数字7。
 *
 * 示例 2 :
 * 输入: 9973
 * 输出: 9973
 * 解释: 不需要交换。
 *
 * 注意:
 * 给定数字的范围是 [0, 108]
 */
public class _0670 {
}


class _0670_Solution {
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();

        int[] last = new int[10];
        for (int i = 0; i < chars.length; i++) {
            last[chars[i] - '0'] = i;
        }

        for (int i = 0; i < chars.length; i++) {
            for (int d = 9; d > chars[i] - '0'; d--) { // bug 修复：d--
                if (last[d] > i) {
                    char tmp = chars[i];
                    chars[i] = chars[last[d]];
                    chars[last[d]] = tmp;
                    return Integer.parseInt(new String(chars));
                }
            }
        }

        return num;
    }
}